package linkedlist;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 判断链表是否有环 II
 */
public class LinkedListCycleII {

  public static void main(String[] args) {
    int[] nums = {3, 2, 0, -4};
    ListNode head = ListNode.generateLinkedList(nums);
    ListNode node1 = ListNode.getIndexNode(head, 1);
    ListNode finalNode = ListNode.getIndexNode(head, 3);
    finalNode.next = node1;
    ListNode ans = detectCycle1(head);
    System.out.println(ans.val);

  }

  /**
   * 使用快慢指针
   *
   * @param head
   * @return
   */
  public static ListNode detectCycle1(ListNode head) {
    if (head == null || head.next == null) {
      return null;
    }
    ListNode quick = head.next.next, slow = head;
    while (quick != slow) {
      if (quick == null || quick.next == null) {
        return null;
      }
      quick = quick.next.next;
      slow = slow.next;
    }
    ListNode ptr = head;
    while (ptr != slow) {
      ptr = ptr.next;
      slow = slow.next;
    }
    return ptr;
  }

  /**
   * 使用Set
   *
   * @param head
   * @return
   */
  public static ListNode detectCycle2(ListNode head) {
    if (head == null || head.next == null) {
      return null;
    }
    Set<ListNode> visited = new HashSet<>();
    ListNode cur = head;
    while (cur != null) {
      if (visited.contains(cur)) {
        return cur;
      }
      visited.add(cur);
      cur = cur.next;
    }
    return null;
  }
}
